package daily;

import java.util.HashMap;
import java.util.Map;

/**
 * @Date 2023-12-31
 * @Author Jonathan
 */
public class LRUCache2 {
    static class LRUNode {
        private Integer key;
        private Integer value;
        private LRUNode next;
        private LRUNode prev;

        public LRUNode() {
        }

        public LRUNode(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    private LRUNode head;
    private LRUNode tail;
    private Integer capacity;
    private Map<Integer, LRUNode> cache;

    public LRUCache2(Integer capacity) {
        this.cache = new HashMap<>();
        this.capacity = capacity;
        head = new LRUNode();
        tail = new LRUNode();
        head.next = tail;
        tail.prev = head;
    }

    public void put(Integer key, Integer value) {
        if (cache.containsKey(key)) {
            LRUNode lruNode = cache.get(key);
            removeNode(lruNode);
        }
        LRUNode node = new LRUNode(key, value);
        cache.put(key, node);
        addNode(node);
        // 超出容量了就头节点删除
        if (cache.size() > capacity) {
            LRUNode evictedNode = head.next;
            removeNode(evictedNode);
            cache.remove(evictedNode.key);
        }
    }

    public Integer get(Integer key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        LRUNode lruNode = cache.get(key);
        removeNode(lruNode);
        addNode(lruNode);
        return lruNode.value;
    }


    private void addNode(LRUNode node) {
        LRUNode prevNode = tail.prev;
        prevNode.next = node;
        node.prev = prevNode;
        node.next = tail;
        tail.prev = node;
    }

    private void removeNode(LRUNode node) {
        LRUNode prevNode = node.prev;
        LRUNode nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    public static void main(String[] args) {
        LRUCache2 cache = new LRUCache2(3);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.put(4, 3);
        System.out.println(cache.get(1));
    }


}
